Solving Linear Congruences
Introduction
When you first learn algebra, one of the most common tasks is solving an equation like $ax = b$.
You look for a number $x$ that makes the equation true.
In modular arithmetic, we face a similar problem, but instead of solving an equation in the usual sense, we solve a congruence: $$ax \equiv b \pmod{n}.$$ This means we want a number $x$ such that when $ax$ is divided by $n$, it leaves the same remainder as $b$.
What a Linear Congruence Is
A linear congruence is a statement of the form: $$ax \equiv b \pmod{n}.$$ This means:
- $a$, $b$, and $n$ are known whole numbers,
- $x$ is the unknown number we want to find,
- and $ax$ and $b$ leave the same remainder when divided by $n$.
For example:
- $3x \equiv 4 \pmod{7}$ means “$3x$ and $4$ have the same remainder when divided by $7$.”
A congruence is like an equation, but instead of asking for exact equality, we ask for equality up to a remainder.
When a Linear Congruence Has a Solution
A key fact:
A congruence $$ax \equiv b \pmod{n}$$ has a solution if and only if the greatest common divisor of $a$ and $n$ divides $b$.
In simpler terms:
- Let $d$ be the greatest common divisor of $a$ and $n$.
- If $d$ does not divide $b$, then no solution exists.
- If $d$ does divide $b$, then solutions exist.
Example:
- $4x \equiv 6 \pmod{10}$
The greatest common divisor of $4$ and $10$ is $2$, and $2$ divides $6$, so solutions exist. - $4x \equiv 7 \pmod{10}$
The greatest common divisor is still $2$, but $2$ does not divide $7$, so no solution exists.
This simple test saves a lot of time.
Reducing the Congruence
If the greatest common divisor $d$ of $a$ and $n$ also divides $b$, then we can simplify the congruence by dividing everything by $d$: $$ax \equiv b \pmod{n}$$ becomes $$\frac{a}{d}x \equiv \frac{b}{d} \pmod{\frac{n}{d}}.$$ This new congruence is simpler and has the same solutions.
Example:
Solve $4x \equiv 6 \pmod{10}$.
- $d = \gcd(4,10) = 2$
- Divide everything by $2$: $$2x \equiv 3 \pmod{5}.$$
Now we have a simpler congruence with the same solutions.
Using Multiplicative Inverses
Once the congruence is simplified so that $a$ and $n$ are coprime (their greatest common divisor is $1$), we can solve it by finding the multiplicative inverse of $a$ modulo $n$.
The multiplicative inverse of $a$ modulo $n$ is a number $a^{-1}$ such that: $$a \cdot a^{-1} \equiv 1 \pmod{n}.$$ If we can find such a number, then solving $$ax \equiv b \pmod{n}$$ is easy:
Multiply both sides by $a^{-1}$: $$x \equiv a^{-1} b \pmod{n}.$$ Example:
Solve $2x \equiv 3 \pmod{5}$.
- We look for a number $k$ such that $2k \equiv 1 \pmod{5}$.
- Try small numbers:
$2 \cdot 3 = 6 \equiv 1 \pmod{5}$. - So the inverse of $2$ modulo $5$ is $3$.
Now multiply both sides by $3$: $$x \equiv 3 \cdot 3 \equiv 9 \equiv 4 \pmod{5}.$$ So the solution is $x \equiv 4 \pmod{5}$.
Finding Inverses by Inspection
For small numbers, you can find inverses by trying possibilities:
To find the inverse of $a$ modulo $n$:
- Try $1, 2, 3, \dots, n-1$
- Multiply each by $a$
- See which one gives remainder $1$ when divided by $n$
Example:
Find the inverse of $7$ modulo $12$.
Try:
- $7 \cdot 1 = 7$ (not $1$ mod $12$)
- $7 \cdot 5 = 35 \equiv 11$ (not $1$)
- $7 \cdot 7 = 49 \equiv 1$ (success)
So the inverse of $7$ modulo $12$ is $7$.
Finding Inverses Using the Euclidean Algorithm
For larger numbers, guessing becomes slow.
The Euclidean Algorithm gives a systematic way to find inverses.
Solving: $$ax \equiv 1 \pmod{n}$$ It is the same as finding a value for $x$ the linear diophantine equation: $$ax + ny = 1$$
Putting It All Together: Solving Any Linear Congruence
To solve $$ax \equiv b \pmod{n},$$ follow these steps:
- Compute $d = \gcd(a,n)$.
- If $d$ does not divide $b$, stop — no solution exists.
- Divide $a$, $b$, and $n$ by $d$.
- Find the inverse of the new $a$ modulo the new $n$.
- Multiply the inverse by the new $b$.
- That gives one solution; all solutions differ by multiples of the new modulus.
Example:
Solve $6x \equiv 9 \pmod{15}$.
- $\gcd(6,15) = 3$, and $3$ divides $9$, so solutions exist.
- Divide everything by $3$: $$2x \equiv 3 \pmod{5}.$$
- The inverse of $2$ modulo $5$ is $3$.
- Multiply: $x \equiv 3 \cdot 3 \equiv 9 \equiv 4 \pmod{5}$.
So the solutions are all numbers of the form: $$x = 4 + 5k,$$
- where $k$ is any whole number.
This is equivalent to: $$x \equiv 4 \pmod{5}$$
Calculator
Checking for solvability
- Given an equation $ax \equiv b \pmod{n}$.
- It is only solvable if: $\gcd(a, n) \mid b$
divides(gcd(a, n), b) divides(gcd(4, 10), 6)
Solving a congruence
- Solves an equation $ax \equiv b \pmod{n}$.
- Returns $m, n$ in the solution: $x \equiv m \pmod{n}$.
solveLinearCongruence(4, 6, 10) solveLinearCongruence(4, 6, 5)
Exercises
Try these to build confidence. Solve each congruence or explain why no solution exists.
- Solve $3x \equiv 2 \pmod{7}$.
- Solve $4x \equiv 6 \pmod{10}$.
- Solve $5x \equiv 1 \pmod{8}$.
- Solve $9x \equiv 12 \pmod{15}$.
- Solve $7x \equiv 3 \pmod{11}$.
- Determine whether $6x \equiv 5 \pmod{9}$ has a solution.
- Solve $8x \equiv 4 \pmod{12}$.
- Find all solutions to $10x \equiv 25 \pmod{35}$.
- Solve $2x \equiv 7 \pmod{9}$.
- Solve $11x \equiv 8 \pmod{13}$.